Data compression, both lossless and lossy, is desirable in many applications in which data is to be stored in, and/or read from, a memory. By compressing data before storage of the data in a memory, the amount of data transferred to the memory may be reduced. An example of data for which data compression is particularly useful is image data, such as depth data to be stored in a depth buffer, pixel data to be stored in a frame buffer and texture data to be stored in a texture buffer. These buffers may be any suitable type of memory, such as cache memory, separate memory subsystems, memory areas in a shared memory system or some combination thereof.
A Graphics Processing Unit (GPU) may be used to process image data in order to determine pixel values of an image to be stored in a frame buffer for output to a display. GPUs usually have highly parallelised structures for processing large blocks of data in parallel. There is significant commercial pressure to make GPUs (especially those intended to be implemented on mobile devices) operate at lower power levels. Competing against this is the desire to use higher quality rendering algorithms on faster GPUs, which thereby puts pressure on a relatively limited resource: memory bandwidth. However, increasing the bandwidth of the memory subsystem might not be an attractive solution because moving data to and from, and even within, the GPU consumes a significant portion of the power budget of the GPU. The same issues may be relevant for central processing units (CPUs) as well as GPUs.
As described above, one way to reduce the amount of data transferred to the memory is to compress the data that is to be transferred to and from the memory. The time taken for data to be compressed and decompressed adds to the latency of the memory read and write operations and therefore may affect the speed at which the GPU operates. Furthermore, the rate at which data is compressed may be permitted to differ from the rate at which that compressed data is decompressed. As an example, the compression process for compressing texture data (which is typically a lossy compression process) may often be permitted to be significantly slower than the decompression process for decompressing the compressed texture data. In contrast the compression processes for compressing depth data for storage in a depth buffer or pixel data for storage in a frame buffer (which are typically lossless compression processes) ideally should be performed at approximately the same rate as the corresponding decompression processes. UK patent number 2451911 discloses a graphics rendering system which can compress a two-dimensional data set.
Variable length encoding schemes allow data to be compressed in a manner such that some portions of data can be represented by fewer encoded bits than other portions of data, with the aim of providing high levels of compression (which may differ) across the different portions of data. However, allowing the number of bits used to represent different encoded data values to vary increases the complexity of decoding the encoded data quickly. For example, without analysing the encoded data (e.g. decoding each of the encoded data values in sequence) it can be difficult to determine where the boundaries between different encoded data values lie.
UK patent number 2530312 describes a data compression system in which 8×8 blocks of image data are compressed by performing colour decorrelation, spatial decorrelation and entropy encoding, and then packing the resulting encoded data values into data packets for storage. In the system described in that patent, a row of data values from a block is processed per iteration. A modified version of Exponential Golomb coding is used for the entropy encoding wherein each coefficient stored a prefix to indicate a range of values that were then identified by a suffix. Having a prefix and suffix for each encoded coefficient makes decoding multiple values simultaneously difficult because it is not simple to quickly determine the positions of the boundaries between encoded bits.